package array;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;

public class EraseOverlapIntervals435 {

    @Test
    public void test() {
        eraseOverlapIntervals(new int[][]{new int[]{1,2}, new int[]{2,3}, new int[]{3,4}, new int[]{1,3}});
        eraseOverlapIntervals(new int[][]{new int[]{1,2}, new int[]{1,2}, new int[]{1,2}});
        eraseOverlapIntervals(new int[][]{new int[]{1,2}, new int[]{2,3}});
    }

    // 思路: 按右边界排序, 右边界小表明与其他区间相交的可能性小. 但最后得到的集合非唯一解.
    public int eraseOverlapIntervals(int[][] v) {
        Arrays.sort(v, new IntervalComparator());
        int lastEnd = Integer.MIN_VALUE;
        int individuals = 0;
        for (int i = 0; i < v.length; i++) {
            if (v[i][0] >= lastEnd) {
                individuals++;
                lastEnd = v[i][1];
            }
        }
        System.out.format("intervals: %s, erased: %d\n", Arrays.toString(v), v.length-individuals);
        return v.length - individuals;
    }

    static class IntervalComparator implements Comparator<int[]> {
        @Override
        public int compare(int[] a, int[] b) {
            return a[1] - b[1];
        }
    }
}
